home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 135_01 / p.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-03-09  |  1.4 KB  |  67 lines
  1. /*
  2.     p.c---Algorithm P(Probabilistic primality test).  From
  3.     "Seminumerical Algorithms: The Art of Computer Programming",
  4.     Vol. 2, by D. E. Knuth, page 379. This version for BDSc...
  5.  
  6.     by Hugh S. Myers
  7.  
  8.     build:
  9.         n>cc p
  10.         n>clink p vli math
  11.  
  12.     3/17/84
  13.     4/3/84
  14. */
  15.  
  16. #include <bdscio.h>
  17. #define MAX 256
  18.  
  19. main()
  20. {
  21.     char n[MAX], n1[MAX], k[MAX], q[MAX], y[MAX], x[MAX], j[MAX];
  22.  
  23.     printf("Algorithm P prime test\n");
  24.     forever {
  25.         printf("?n ");
  26.         getline(n,MAX);
  27.         if(iseven(n) && (!isequal(n,"2"))) {
  28.             printf("except for 2 all primes are odd!\n");
  29.             continue;
  30.         }
  31.         if(isequal(n,"2")) {
  32.             printf("n is definately prime!\n");
  33.             continue;
  34.         }
  35.         strcpy(n1,decrl(n));
  36.         strcpy(q,n1);
  37.         strcpy(k,"0");
  38.         while(iseven(q)) {
  39.             strcpy(q,sdivl(q,2));
  40.             strcpy(k,incrl(k));
  41.         }
  42.         strcpy(j,"0");
  43.         do {
  44.             strcpy(x,randl(0));
  45.             strcpy(x,modl(x,n));
  46.         } while (sisltl(x,2));
  47.         strcpy(y,modp(x,q,n));
  48.         forever {
  49.             if((iszero(j) && sisequal(y,1)) || isequal(y,n1)) {
  50.                 printf("%s is probably prime\n",n);
  51.                 break;
  52.             }
  53.             if(!iszero(j) && sisequal(y,1)) {
  54.                 printf("%s is not prime\n",n);
  55.                 break;
  56.             }
  57.             strcpy(j,incrl(j));
  58.             if(isltl(j,k))
  59.                 strcpy(y,modp(y,"2",n));
  60.             else {
  61.                 printf("%s is not prime\n",n);
  62.                 break;
  63.             }
  64.         }
  65.     }
  66. }
  67.